package com.squirrel.michale.sort2;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/25 8:31 AM
 * @company Michale Squirrel
 * @link
 * @description 剑指 Offer 51. 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 * <p>
 * <p>
 * 限制：
 * <p>
 * 0 <= 数组长度 <= 50000
 * <p>
 * 通过次数181,688提交次数365,921
 */
public class Offer51 {


    public int reversePairs(int[] nums) {

        return process(nums, 0, nums.length - 1);
    }

    private int process(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int middle = left + ((right - left) >> 1);
        int leftPair = process(arr, left, middle);
        int rightPair = process(arr, middle + 1, right);
        int mergePair = merge(arr, left, middle, right);
        return leftPair + rightPair + mergePair;
    }

    private int merge(int[] arr, int left, int middle, int right) {
        int[] help = new int[right - left + 1];

        int helpIndex = 0;
        int leftIndex = left;
        int rightIndex = middle + 1;
        int pairCount = 0;

        while (leftIndex <= middle && rightIndex <= right) {
            pairCount += arr[leftIndex] > arr[rightIndex] ? (middle - leftIndex +1 ) : 0;
            help[helpIndex++] = arr[leftIndex] <= arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
        }

        while (leftIndex <= middle) {
            help[helpIndex] = arr[leftIndex];
            helpIndex++;
            leftIndex++;
        }

        while (rightIndex <= right) {
            help[helpIndex] = arr[rightIndex];
            helpIndex++;
            rightIndex++;
        }

        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return pairCount;
    }


    public static void main(String[] args) {

        Offer51 offer51 = new Offer51();
        int[] nums = new int[]{7, 5, 6, 4};
        System.out.println(offer51.reversePairs(nums));

        int[] nums2 = new int[]{2, 4, 3, 5, 1};
        // 预期结果5
        System.out.println(offer51.reversePairs(nums2));

    }


}
